As is known, routing protocols are used in packet-switched networks for computer communications and are implemented by every switching node in the network to forward data packets. In the Internet, these nodes are called routers.
There are two main classes of routing protocols: the distance-vector routing protocols and the link-state routing protocols. In a distance-vector routing protocol, such as the Routing Information Protocol (RIP), each node periodically exchanges reachability information with its neighbors, while in a link-state routing protocol, such as the Open Shortest Path First (OSPF) protocol and the Intermediate System to Intermediate System (IS-IS) protocol, connectivity information is passed between the nodes to construct connectivity maps.
In particular, in a link-state routing protocol, each node receives from all the other nodes a map of the connectivity of the network, in the form of a graph showing which nodes are connected to which other nodes, and independently computes the best next hop for every possible destination in the network. This is done by using only a local copy of the map, and without communicating in any other way with any other node. The collection of best next hops forms the routing table for the node.
Link-state routing protocols are commonly used for intra-domain routing, i.e. are exploited to transport routing information among routers of the same routing domain, also known as Autonomous System (AS), which is a region of a network under a single administrative domain.
In OSPF-based Autonomous Systems, each router periodically floods immediate connectivity information to all the other routers in the Autonomous System by means of Link-State Advertisement (LSA) messages enclosed into Link-State Update (LSU) messages. The LSA messages contain the routing information from which each router constructs a consistent view of the network topology, used to correctly route data packets from their source to their-destination.
Anomaly detection is a well known approach to intrusion detection in network and computer security, and is generally based on statistical models computed for the normal behaviour of an object (users, software products or networks), and on the subsequent measure of the distance of the monitored “live” behaviour of the object from the normal one.
Currently, several methods are known in the literature implementing anomaly detection for routing protocols, most of which are based on known statistical approaches, like the so-called Next-generation Intrusion Detection Expert System/STATistical (NIDES/STAT) Intrusion Detection System (IDS) or the so-called Property-Oriented detection approach for OSPF. For a detailed description of these approaches reference may be made to D. Qu, B. Vetter, F. Wang, R. Narayan, S. Wu, Y. Jou, F. Gong, C. Sargor, Statistical Anomaly Detection for Link-State Routing Protocols, Sixth International Conference on Network Protocols, 1998, page 62, and respectively to F. Wang, F. Gong, F. S. Wu, H. Qi, Design and Implementation of Property-Oriented Detection for Link-State Routing Protocols, in Proceedings of the 2001 IEEE Workshop on Information Assurance and Security, US Military Academy, West Point, N.Y., June 2001, ISBN 0-7803-9814-9 IEEE.
In particular, in Statistical Anomaly Detection for Link-State Routing Protocols, a statistical anomaly detection approach for link-state routing protocols is disclosed, which is based on the NIDES/STAT IDS and was mainly tested on simulated insider attacks against Open Shortest Path First (OSPF) protocol.
The NIDES approach to intrusion detection is to construct a short-term statistical profile of the monitored object and to compare it with a long-term profile generated during a previous training session The profiles are basically the probability distributions of several intrinsic object variables, and they are compared using a modified test. Among the variables taken into account for attack detection, there are variables that measure the routing activity intensity (e.g. the volume of OSPF traffic in a time interval), the distribution of OSPF packets type, 3 fields of the Link State Advertisement (LSA), i.e., age, checksum, and sequence number, CPU usage on routers, etc. The fields are examined independently and the values therein are compared individually with respective predefined values (from the OSPF protocol standard) to generate one of the following coarse alarms, such as “invalid checksum”, “invalid sequence number”, “init sequence number”, “max sequence number”, and “normal”. In detail, the comparison is aimed at checking whether the LSA checksum is correct, the LSA age is lower than or equal to the maximum admissible value (standardized in 3600 s), and the LSA sequence number is not equal to a sequence initial number or a maximum sequence number (also standardized).
In Design and Implementation of Property-Oriented Detection for Link-State Routing Protocols, a generic protocol analysis is applied to the OSPF, reducing the whole properties space to a significant subset in order to limit the complexity of the task. The OSPF case study is simplified by considering only flat or mono area routing, only point to point networks, and by not taking into account the LSA type 5 messages, used when a router acts as an Autonomous System Border Router (ASBR).
In other network security-related areas, some anomaly detection approaches are known which use machine learning paradigms like traditional binary Support Vector Machines (SVMs) or one-class SVMs.
Specifically, SVMs are a class of machine learning algorithms for classification/regression that are particularly useful for high dimensional-input data with either large or small training sets. SVMs algorithms work by mapping the input feature space into a high-dimensional feature space, and computing linear functions on those mapped features in the high-dimensional feature space.
SVMs are generally trained through supervised learning, in which the best function that relates the output data to the input data is computed, and the goodness of this function is judged by its ability to generalize on new inputs, i.e. inputs which are not present in the training set. For a detailed description of learning methods for SVMs, reference may be made to N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines and other kernel-based learning methods, pp. 93-122, Cambridge University Press, 2000.
In S. Kaplantzis, N. Mani, A Study on Classification Techniques for Network Intrusion Detection, presented at the IASTED International Conference on Networks and Communication Systems, Thailand, SVMs are used for detecting intrusions and misbehaviours in TCP/IP networks.
In particular, SVMs are used to perform misused detection, hence to detect known attacks. The SVMs are trained on existent attack data, in particular on the Defense Advanced Research Projects Agency (DARPA) database for IDS evaluation (benchmark created by Lincoln Laboratory of Massachusetts Institute of Technology from 1998 to 0.2000). The features on which these SVMs work are the 41 TCP connection features included in the DARPA database or on a subset of these features. The attacks included in the database are probing attacks, Denial-of-Service (DoS) attacks, user to root access and remote to user access.
Another area in which the use of SVMs was proposed is intrusion detection in wireless ad hoc networks. In this case the intrusion detection functionality is meant to detect anomalous behaviour in network traffic, which also includes routing traffic. Hence, the SVM features also include some routing traffic information: the rate of routing requests and responses received and sent by a node and the number of modifications (such as add, remove, find) performed on the routing tables of each node. For a detailed description of intrusion detection in wireless ad hoc networks, reference may be made to P. Fu, D. Zhang, L. Wang, Z. Duan, Intelligent Hierarchical Intrusion Detection System for Secure Wireless Ad Hoc Network, Conference Title: Advances in Neural Networks—ISNN 2005, Second International Symposium on Neural Networks, Proceedings, Part III (Lecture Notes in Computer Science Vol. 3498) Part Vol. 3 p. 482-7 Vol. 3, and to H. Deng, Q.-A. Zeng, D. P. Agrawal, SVM-based Intrusion Detection System for Wireless Ad Hoc Networks, in Proceedings of the IEEE Vehicular Technology Conference, October 2003, IEEE 58th Volume 3, Issue, 6-9 October 2003 Page(s): 2147-2151 Vol. 3.